package src.BlueBridge.GreedyStrategyAndDynamicProgramming;

import java.util.Arrays;
import java.util.Scanner;

/**
 * 有N个人期望去跨越一条河，但是只有一只船，这只船一次只能装两个人
 * 两个人一组的话划船速度是由慢的人决定的
 * T为测试用例的数量，每一组有N个人，下一行是他们各自的速度
 * 1
 * 4
 * 1 2 5 10
 * 要求输出最少的时间
 *
 * 策略一:
 * 1,10过河
 * 1回来
 * 1,5过河
 * 1回来
 * 1,2过河
 * 总共花费:19s
 *
 * 策略二:
 * 快的先过
 * 1,2过河
 * 1回来
 * 5,10过河
 * 2回来
 * 1,2过河
 * 使得两边都保留一个快的
 * 花费:17s
 *
 * 假设四人是a b c d
 * 策略一:
 * ad过河
 * a回来
 * ac过河
 * a回来
 * ab过河
 * 花费:d+a+c+a+b=2a+b+c+d
 * 策略二:
 * ab过河
 * a回来
 * cd过河
 * b回来
 * ab过河
 * 花费:b+a+d+b+b=a+3b+d
 *
 * 两边抵消:
 * 也即是a+c 和  2b的比较
 * 此时两边值有大有小
 */

public class _2快速渡河 {
    public static void main(String[] args) {
        // 处理输入
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        for (int i = 0 ; i < T ; i++) {
            int n = sc.nextInt();
            int[] speed = new int[n];
            for (int j = 0 ; j < n ; j++) {
                speed[j] = sc.nextInt();
            }
            // 排序
            Arrays.sort(speed);
            f(n, speed);
        }
    }

    /**
     * speed已经排序
     * @param n 人数
     * @param speed
     */
    public static void f(int n, int[] speed) {
        // 将总人数赋值给左边的总人数
        int left = n;
        // 最少的时间
        int ans = 0;
        while (left > 0) {
            if (left == 1) {// 只有1个人
                ans += speed[0];
                break;
            }else if (left == 2) {// 有2人
                ans += speed[1];
                break;
            }else if (left == 3) {// 有3人
                ans += speed[0] + speed[1] + speed[2];
                break;
            }else {
                // 1,2出发，1返回，最后两名出发，2返回
                int s1 = speed[1] + speed[0] + speed[left - 1] + speed[1];
                // 1,3出发，1返回，1,4出发，1返回
                int s2 = speed[left - 1] + speed[left - 2] + 2 * speed[0];
                ans += Math.min(s1, s2);
                // 左侧是渡河的起点，left代表左侧的剩余人数
                left -= 2;
            }
        }
        System.out.println(ans);
    }
}
